/**
 *  @file .
 *  @author wangxiaowei <wangxiaowei0303@163.com>
 *  @date 2015-02-11-10.09
 *  一列有 80 个'C'.
 *  1. 红黑树的整体结构;
 *    * 红黑树的根节点的父节点为哨兵,并不为0.
 *    * 并没有使用算法导论中介绍的叶子节点(外部节点);而是若一个结点没有左子树,或者右子树
 *      则指针置为0,则此时合法红黑树的性质是:
 *      * 根节点总是黑色;
 *      * 若节点的颜色是红色,则除非它没有孩子节点,否则其孩子节点总是黑色.
 *      * 对于红黑树中的任何一个节点,它到所有后代叶子节点的简单路径上具有相同数目的黑色节点.
 *  2. 红黑树中节点的关系;
 *    * 对于红黑树中的任何一个节点,其左节点的键始终不大于该结点的键,其右孩子的键始终不小于
 *      该结点的键;
 *    * 在插入节点时,如将节点 a 插入到节点 b 上,则仅当 a 的键小于 b 的键时,才会将 a 插入到
 *      b 的左孩子上;否则将插入到 b 的右孩子上.
 */


#ifndef org_wxw_std_study_include_bits_stl_tree_h_
#define org_wxw_std_study_include_bits_stl_tree_h_

#include "my.stl.inc/bits/move.h"

namespace mystd{


enum _Rb_tree_color{
	_S_red = 0,
	_S_black
};

struct _Rb_tree_node_base{
	typedef _Rb_tree_node_base *_Base_ptr;
	typedef const _Rb_tree_node_base *_Const_Base_ptr;

	_Rb_tree_color _M_color;
	_Base_ptr _M_parent;
	_Base_ptr _M_left;
	_Base_ptr _M_right;

	/**
	 *  x 指向着二叉搜索树,_S_minimum(),_S_maximum() 用于获取这颗二
	 *  叉搜索树的最小值,最大值;算法可以参考
	 *  算法导论/二叉搜索树/最值算法.
	 *  @param x 要求:不能为0,
	 */
	static _Base_ptr
	_S_minimum(_Base_ptr x);
	static _Const_Base_ptr
	_S_minimum(_Const_Base_ptr x);
	static _Base_ptr
	_S_maximum(_Base_ptr x);
	static _Const_Base_ptr
	_S_maximum(_Const_Base_ptr x);
};

template<typename _Val>
struct _Rb_tree_node: public _Rb_tree_node_base{
	typedef _Rb_tree_node *_Link_type;

	_Val _M_value_field;

	_Val*
	_M_valptr(){
		return mystd::__addressof(_M_value_field);
	}

	const _Val*
	_M_valptr()const{
		return mystd::__addressof(_M_value_field);
	}
};

/// _Rb_tree_iterator,迭代器,行为就是一个指针,指向着红黑树中的一个结点
template<typename T>
struct _Rb_tree_iterator{
	typedef _Rb_tree_iterator<T> _Self;
	typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
	typedef _Rb_tree_node<T> *_Link_type;

	/// 构建一个默认迭代器,此时 _M_node 为 0.
	_Rb_tree_iterator();

	/// 根据红黑树中的节点构建迭代器,此时迭代器指向着该节点
	explicit
	_Rb_tree_iterator(_Link_type x);

	/// 迭代器自增,即迭代器移向当前所指结点的后继
	_Self&
	operator++(){
		_M_node = _Rb_tree_increment(_M_node);// 获取 _M_node 的后继
		return *this;
	}

	/// 迭代器自减.移向当前所指结点的前驱
	_Self&
	operator--(){
		_M_node = _Rb_tree_decrement(_M_node);// 获取 _M_node 的前驱.
		return *this;
	}

	_Base_ptr _M_node;
};

/// const iteator,即不能通过这个迭代器去修改其所指元素的值
template<typename T>
struct _Rb_tree_const_iterator{
	typedef _Rb_tree_const_iterator<T> _Self;
	typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
	typedef const _Rb_tree_node<T> *_Link_type;
	typedef _Rb_tree_iterator<T> iterator;

	/// 构建一个空的迭代器,此时 _M_node = 0.
	_Rb_tree_const_iterator();

	/// 根据红黑树中的节点构建迭代器,此时迭代器指向着该节点
	explicit
	_Rb_tree_const_iterator(_Link_type x);

	/// 构建一个非 const 迭代器来构建一个 const_iterator 迭代器.
	_Rb_tree_const_iterator(const iterator &);

	/// 等同于 const_cast 转换,去除当前 const 迭代器的 const 属性.
	iterator
	_M_const_cast()const;

	/// 迭代器自增,即迭代器移向当前所指结点的后继
	_Self&
	operator++(){
		_M_node = _Rb_tree_increment(_M_node);// 获取 _M_node 的后继
		return *this;
	}

	/// 迭代器自减.移向当前所指结点的前驱
	_Self&
	operator--(){
		_M_node = _Rb_tree_decrement(_M_node);// 获取 _M_node 的前驱.
		return *this;
	}

	_Base_ptr _M_node;
};

/**
 *  将节点 x 插入在节点 p 上,并进行调整维护红黑树的性质不变,并更新
 *  header,使其成员始终指向着红黑树的根节点,红黑树最左端,最右端的节点.
 *  @param insert_left 若为真,则表明 x 插入到 p 的左子树上;
 */
void
_Rb_tree_insert_and_rebalance(const bool insert_left,
							_Rb_tree_node_base* x,
							_Rb_tree_node_base* p,
							_Rb_tree_node_base& header) throw ();

/**
 *  在 header 确定的红黑树中移除 z 指向的节点,然后进行调整以维护红黑树的性
 *  质不变,并且若需要则更新 header 成员的值使其指向新的根节点,最左端节点,
 *  最右端节点.然后返回一个指针,指向被移除的节点.即并没有释放被移除节点
 *  所占的内存.
 */
_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const z,
							 _Rb_tree_node_base &header);

/**
 *  _Rb_tree,红黑树.
 *  @tparam Val 红黑树节点中保存的值类型,此时红黑树结点的类型为
 *				_Rb_tree_node<Val>;Val 类型包含了键,以及卫星数据
 *				关于"键,卫星数据"的概念参考算法导论/二叉搜索树
 *  @tparam Key 红黑树中结点的键的类型
 *  @tparam KeyOfValue 该类型重载了 operator(),可以从 Val 类型的
 *					   对象中提取出键的值.具体可以参考 std::multimap
 *                     的声明.
 *  @tparam Compare 参见 http://my.oschina.net/dream0303/blog/351499
 */
template<typename Key,typename Val,typename KeyOfValue,
		 typename Compare,typename Alloc=allocator<Val> >
class _Rb_tree{

	/// _Node_allocator 就是 allocator<_Rb_tree_node<Val> >
	typedef typename __gnu_cxx::__alloc_traits<Alloc>::
	template rebind<_Rb_tree_node<Val> >::other _Node_allocator;

protected:
	typedef _Rb_tree_node_base* _Base_ptr;
	typedef const _Rb_tree_node_base* _Const_Base_ptr;
	typedef _Rb_tree_node<_Val>* _Link_type;
	typedef const _Rb_tree_node<_Val>* _Const_Link_type;

private:

	/**
	 *  _Reuse_or_alloc_node,_Alloc_node 都是仿函数,所以除了构造函数外,最重要
	 *  的就是 operator() 函数,该函数的原型如下:
	 *  	template<typename ValType>
	 *		_Link_type
	 *		operator()(const ValType &val);
	 *  即 operator() 会创建一个节点,并将值 val 保存在该节点中.
	 *  1. 在 _Reuse_or_alloc_node 中,可能会重用已经存在的节点,而不总是分配
	 *     新的节点.
	 *  2. 在 _Alloc_node 中,总是分配新的节点.
	 */
	struct _Reuse_or_alloc_node{
	};// struct _Reuse_or_alloc_node

	struct _Alloc_node{
		_Alloc_node(_Rb_tree &t):
			_M_t(t) { ; }

		template<typename ValType>
		_Link_type
		operator()(const ValType &val)const{
			return _M_t._M_create_node(val);
		}
	private:
		_Rb_tree &_M_t;
	};// _Alloc_node

public:
	typedef Key key_type;
	typedef Val value_type;
	typedef Alloc allocator_type;

	/**
	 *  获取当前红黑树使用的用于给节点分配内存的分配器.
	 *  分配器存放在 _Rb_tree_impl 对象中,若 _Rb_tree_impl 的实现如:
	 *  struct _Rb_tree_impl{
	 *  	_Node_allocator _M_node_allocator;
	 *  	KeyCompare _M_key_compare;
	 *  	_Rb_tree_node_base _M_header;
	 *  	size_type _M_node_count;
	 *  }
	 *  则此时函数就直接 return _M_impl._M_node_allocator 即可
	 *  但由于 _Rb_tree_impl 以一种隐含的方式保存了分配器,所以
	 *  实现如下:
	 */
	_Node_allocator&
	_M_get_Node_allocator(){
		return *static_cast<_Node_allocator*>(&_M_impl);
	}

	const _Node_allocator&
	_M_get_Node_allocator() const;

	// 我觉得这个函数没啥意义
	allocator_type
	get_allocator()const{
		return allocator_type(_M_get_Node_allocator());
	}

protected:
	/**
	 *  _M_get_node(),_M_put_node 的味道有点像 node pool.
	 *  _M_get_node() 从 node pool 中获取一个未使用的节点,
	 *                然后返回指针.
	 *  _M_put_node() 相当于将一个节点放入到 node pool 中.
	 */
	_Link_type
	_M_get_node(){
		return _M_get_Node_allocator().allocate(1);
	}

	void
	_M_put_node(_Link_type p){
		_M_get_Node_allocator().deallocate(p,1);
	}

	/**
	 *  将 node 指向的红黑树节点中保存的值设置为 x.
	 *  一般 node 是刚从 _M_get_node() 中返回
	 */
	void
	_M_construct_node(_Link_type node,const value_type &x){
		try{
			get_allocator().construct(node->_M_valptr(),x);
		}catch(...){
			_M_put_node(node); // 构造失败,回收内存.
			throw;
		}
	}

	/// 创建一个值为 x 的红黑树节点,并返回该节点的指针.
    _Link_type
    _M_create_node(const value_type &x){
    	_Link_type node = _M_get_node();
    	_M_construct_node(node,x);
    	return node;
    }

    /// 销毁 p 所指红黑树节点中保存的值,但不回收节点 p.
    void
    _M_destroy_node(_Link_type p){
    	get_allocator().destroy(p->_M_valptr());
    }

    /// 销毁 p 所指节点中保存的值,并回收节点 p.
    void
    _M_drop_node(_Link_type p){
    	_M_destroy_node(p);
    	_M_put_node(p);
    }

	/**
	 *  克隆节点,新节点的值与颜色与 node 相同,新节点的左孩子指针,右孩子指针
	 *  均设置为0,并没有父节点指针没有设置.
	 *  @tparam NodeGen _Reuse_or_alloc_node,_Alloc_node 的一种
	 */
	template<typename NodeGen>
	_Link_type
	_M_clone_node(_Const_Link_type node,NodeGen &nodeGen){
		_Link_type newNodePtr = nodeGen(*node->_M_valptr())
		newNodePtr->_M_color = node->_M_color;
		newNodePtr->_M_left = 0;
		newNodePtr->_M_right = 0;
		return newNodePtr;
	}
protected:

	/**
	 *  _Rb_tree_imple,保存了一棵红黑树所需要的所有成员.
	 *  有用于分配节点的 _Node_allocator;
	 *  用于比较的 _M_key_compare
	 *  红黑树的根,最左端的节点,最右端的节点;存放在 _M_header 中
	 *  红黑树中节点的个数.
	 *  其实这里也可以这样写:
	 *  struct _Rb_tree_impl{
	 *  	_Node_allocator _M_node_allocator;
	 *  	KeyCompare _M_key_compare;
	 *  	_Rb_tree_node_base _M_header;
	 *  	size_type _M_node_count;
	 *  }
	 *  只不过这种写法与下面的写法相比;会多占 3 或者 7 个字节.
	 *  具体分析参见 TODO
	 */
	template<typename KeyCompare,bool>
	struct _Rb_tree_impl: public _Node_allocator{
		KeyCompare _M_key_compare;
		/**
		 *  _M_header 存放着红黑树的根节点,最左端节点,最右端节点;
		 *  _M_header._M_parent,指向着红黑树的根节点.
		 *  _M_header._M_left,指向着红黑树最左端的节点,即最小值.
		 *  _M_header._M_right,指向着红黑树最右端的节点,即最大值.
		 */
		_Rb_tree_node_base _M_header;
		size_type _M_node_count;

		_Rb_tree_impl():
			_Node_allocator(),_M_key_compare(),
			_M_header(),_M_node_count(0)
		{
			_M_initialize();
		}

		_Rb_tree_impl(const KeyCompare &keyCompare,
					  const _Node_allocator &nodeAllocator):
			_Node_allocator(nodeAllocator),
			_M_key_compare(keyCompare),
			_M_header(),
			_M_node_count(0)
		{
			_M_initialize();
		}

		void
		_M_reset(){
			_M_header._M_parent = 0;
			_M_header._M_left = &_M_header;
			_M_header._M_right = &_M_header;
			_M_node_count = 0;
		}
	private:

		void
		_M_initialize(){
			_M_header._M_color = _S_red;
			_M_header._M_parent = 0;
			_M_header._M_left = &_M_header;
			_M_header._M_right = &_M_header;
		}
	};// struct _Rb_tree_impl

	_Rb_tree_impl<Compare> _M_impl;

protected:
	_Base_ptr&
	_M_root(){
		return this->_M_impl._M_header._M_parent;
	}

	_Const_Base_ptr
	_M_root() const{
		return this->_M_impl._M_header._M_parent;
	}

	_Base_ptr&
	_M_leftmost(){
		return this->_M_impl._M_header._M_left;
	}

	_Const_Base_ptr
	_M_leftmost() const {
		return this->_M_impl._M_header._M_left;
	}

	_Base_ptr&
	_M_rightmost() {
		return this->_M_impl._M_header._M_right;
	}

	_Const_Base_ptr
	_M_rightmost() const {
		return this->_M_impl._M_header._M_right;
	}

	_Link_type
	_M_begin(){
		return static_cast<_Link_type>( this->_M_impl._M_header._M_parent );
	}

	/**
	 *  参考 std::multimap::end().
	 *  此时并没有返回最右端的节点,而是返回 _M_header,所以
	 *  _M_header 可以看做哨兵一般的存在.
	 */
	_Link_type
	_M_end(){
		return static_cast<_Link_type>( &this->_M_impl._M_header );
	}

	static _Base_ptr
	_S_minimum(_Base_ptr root) {
		return _Rb_tree_node_base::_S_minimum(root);
	}

	static _Const_Base_ptr
	_S_minimum(_Const_Base_ptr root) {
		return _Rb_tree_node_base::_S_minimum(root);
	}

	static _Base_ptr
	_S_maximum(_Base_ptr root) {
		return _Rb_tree_node_base::_S_maximum(root);
	}

	static _Const_Base_ptr
	_S_maximum(_Const_Base_ptr root) {
		return _Rb_tree_node_base::_S_maximum(root);
	}


public:
	typedef _Rb_tree_iterator<value_type> iterator;
	typedef _Rb_tree_const_iterator<value_type> const_iterator;

private:

	/**
	 *  获取 key 在红黑树中的插入位置,若 key 已经存在,则返回(key所在节点的
	 *  地址,0);若 key 不存在,则返回(0,key插入节点的指针).
	 *  理论上调用该函数时,每个键最能只能存在一个,但如果在当前红黑树中已经
	 *  有多个 key,则返回(最后一个key所在节点的地址,0);这里的最后一个是指
	 *  中序遍历形成的有序表中最末端的.
	 */
	pair<_Base_ptr,_Base_ptr>
	_M_get_insert_unique_pos(const key_type &key){
		_Link_type x = _M_begin();
		_Link_type p = _M_end();
		bool comp = true;
		while( x != 0 ){
			y = x;
			comp = _M_impl._M_key_compare(key,_S_key(x))
			x = comp ? x->_M_left : _M_right;
		}
		// 当循环结束时,x==0,y 指向着 x 的上一个节点,若 comp 为真,
		// 则表明 key < y->key;否则表示 key >= y->key;
		iterator j(y);
		if(comp){
			if( j==begin() )
				return pair<_Base_ptr,_Base_ptr>(x,y);
			else
				--j;// j 指向 y 的前驱
			// 此时可以证明 j->key <= key,具体如何证明,我忽然想不起来了~_~.
			// 大概看了一天没脑汁了吧
		}
		// j->key < key;则返回插入位置 y.
		if(_M_impl._M_key_compare(_S_key(j._M_node),key))
			return pair<_Base_ptr,_Base_ptr>(x,y);
		// 否则 j->key >= key;结合 j->key <= key;可知 j->key==key;所以返回 j
		return pair<_Base_ptr,_Base_ptr>(j._M_node,0);
	}

	/**
	 *  获取 key 在红黑树中的插入位置,此时允许键重复.
	 *  内部确定插入位置的算法,就和算法导论/二叉搜索树一样.
	 *  返回(0,插入位置).
	 */
	pair<_Base_ptr,_Base_ptr>
	_M_get_insert_equal_pos(const key_type &key){
		_Link_type p = _M_end();
		_Link_type x = _M_begin();
		while(x!=0){
			p = x;
			x = _M_impl._M_key_compare(key,_S_key(x)) ?
					x->_M_left :
					x->_M_right;
		}
		return pair<_Base_ptr,_Base_ptr>(x,p);
	}

	/**
	 *  利用 NodeGen 生成一个结点,存放值 val,然后将该结点插入在 p 上,即 p 是
	 *  新节点的父节点.
	 *  @param x 意义不明,在目前的调用中,x 始终为0.TODO
	 */
	template<typename NodeGen>
	iterator
	_M_insert_(_Base_ptr x,_Base_ptr p,const value_type &val,NodeGen &nodeGen){
		_Link_type newNodePtr = nodeGen(val);
		// 若为真,则表明新节点应插入在 p 的左侧;否则插入在 p 的右侧.
		bool insert_left = x!=0 || p==_M_end() ||
						   _M_impl._M_key_compare(KeyOfValue()(val),_S_key(p));
		_Rb_tree_insert_and_reblance(insert_left,newNodePtr,p,
									_M_impl._M_header);
		++_M_impl._M_node_count;
		return iterator(newNodePtr);
	}



    /**
     *  复制一棵红黑树.
     *  此时 oneTreeRoot 指向着一棵红黑树的根节点,此时会创建一棵新的红黑树,
     *  新红黑树与 oneTreeRoot 指向的红黑树完全相同,此时将新红黑树的根节点
     *  的父节点指向着 parent.然后返回新红黑树的根节点的指针.
     *  @param oneTreeRoot 要求:非0,指向着一棵红黑树.
     *  @param parent 新红黑树根节点的父节点.
     *  @tparam NodeGen 可能是 _Reuse_or_alloc_node 或者 _Alloc_node
     *  @return 新红黑树根节点的指针.
     *  可以看下面 _M_copy() 的递归实现来加深理解.
     */
	template<typename NodeGen>
	_Link_type
	_M_copy(_Const_Link_type oneTreeRoot,_Link_type parent,NodeGen &nodeGen){
		_Link_type root = _M_clone_node(oneTreeRoot,nodeGen);
		root->_M_parent = parent;
		if(oneTreeRoot->_M_right != 0)
			root->_M_right = _M_copy(oneTreeRoot->_M_right,root,nodeGen);
		oneTreeRoot = oneTreeRoot->_M_left;
		parent = root;
		while(oneTreeRoot != 0){
			_Link_type y = _M_clone_node(oneTreeRoot,nodeGen);
			y->_M_parent = parent;
			parent->_M_left = y;
			if(oneTreeRoot->_M_right != 0)
				y->_M_right = _M_copy(oneTreeRoot->_M_right,y,nodeGen);
			oneTreeRoot = oneTreeRoot->_M_left;
			parent = y;
		}
		return root;
		/* 以下是递归实现 */
//		_Link_type root = _M_clone_node(oneTreeRoot,nodeGen);
//		root->_M_parent = parent;
//		if(oneTreeRoot->_M_right != 0)
//			root->_M_right = _M_copy(oneTreeRoot->_M_right,root,nodeGen);
//		if(oneTreeRoot->_M_left != 0)
//			root->_M_left = _M_copy(oneTreeRoot->_M_left,root,nodeGen);
//		return root;
	}

	_Link_type
	_M_copy(_Const_Link_type oneTreeRoot,_Link_type parent){
		_Alloc_node nodeGen(*this);
		return _M_copy(oneTreeRoot,parent,nodeGen);
	}

	/**
	 *  销毁一棵红黑树.
	 *  root 指向着一棵红黑树,此时会回收该红黑树所有节点所占的内存.
	 */
	void
	_M_erase(_Link_type root){
		_Link_type left = 0;
		while(root != 0){
			_M_erase(root->_M_right);
			left = root->_M_left;
			_M_drop_node(root);
			root = left;
		}
		/* 递归实现,如下 */
//		if(root == 0)
//			return ;
//		if(root->_M_right != 0)
//			_M_erase(root->_M_right);
//		if(root->_M_left != 0)
//			_M_erase(root->_M_left);
//		_M_drop_node(root);
//		return ;
	}

	/**
	 *  在一个以 root 的红黑树中查找 key 的存在,可以试想着按照中序遍历算法
	 *  得到该红黑树的有序表,此时若 key 存在,则返回其在有序表中最早出现时
	 *  的迭代器,若 key 不存在,则返回其后继(即在有序表中第一个大于 key 的节
	 *  点),若不存在后继,则返回 y.如下:
     *                 ------
     *                 | 7  |
     *                /------\
     *         ------/        \-----
     *         | 5b |         | 9a |
     *         /----\         -----\
     *  ------/      \-----         \-----
     *  | 5a |       | 6  |         | 10 |
     *  ------       ------         ------
     *  此时中序遍历的有序表: 5a;5b;6;7;9a;10
	 *  查找 4 时,返回的迭代器指向着"5a",因为在有序表中,5a 是第一个大于 4 的.
	 *  查找 5 时,返回的迭代器指向着"5a",而不是"5b",虽然"5b"是最遇到的.
	 */
	iterator
	_M_lower_bound(_Link_type root,_Link_type y,const Key &key){
		while(root != 0){
			if(_M_impl._M_key_compare(_S_key(root),key))
				root = root->_M_right;
			else{
				// 此时表明 root 应该与 key 在一个位置,或者在 key 的后方
				// 即 key 在 root 的前方,或者与 root 一个位置,
				// 即 key 在 root 的左子树上.
				y = root;
				root = root->_M_left;
			}
		}
		return iterator(y);
	}

	/**
	 *  无论 k 在以 root 为根的红黑树中是否存在,都返回一个迭代器,指向着第
	 *  一个比 k 大的节点.如 _M_lower_bound() 文档中介绍的树,
	 *  查找 5 时,返回指向 6 的迭代器;
	 *  查找 4 时,返回指向着 5a 的迭代器.
	 */
	iterator
	_M_upper_bound(_Link_type root,_Link_type y,const Key &k){
		while(root != 0){
			if(_M_impl._M_key_compare(k,_S_key(root))){
				y = root;
				root = root->_M_left;
			}else
				root = root->_M_right;
		}
		return iterator(y);
	}

public:
	_Rb_tree(const _Rb_tree &oneTree):
		_M_impl(oneTree._M_impl._M_key_compare,oneTree._M_get_Node_allocator())
	{
		_M_root() = _M_copy(oneTree._M_begin(),_M_end());
	    _M_leftmost() = _S_minimum(_M_root());
	    _M_rightmost() = _S_maximum(_M_root());
	    _M_impl._M_node_count = oneTree._M_impl._M_node_count;
	}

	~_Rb_tree(){
		_M_erase(_M_begin());
	}

	/**
	 *  将 x 赋值给当前红黑树,除了所有节点被赋值之外,x 使用的比较对象,用于
	 *  给节点分配内存的对象来都赋给了当前红黑树.
	 */
	_Rb_tree&
	operator=(const _Rb_tree &x);

	iterator
	begin(){
		return iterator(static_cast<_Link_type>(_M_impl._M_header._M_left));
	}

	/// 注意此时 end() 返回的是 _M_header 的地址.
	iterator
	end(){
		return iterator(static_cast<_Link_type>(&_M_impl._M_header));
	}

	/**
	 *  释放红黑树所有节点所占的内存,然后重置内部变量的值,使其状态变为
	 *  红黑树最初创建时一样.
	 */
	void
	clear(){
		_M_erase(_M_begin());
		_M_impl._M_reset();
	}

	/**
	 *  在红黑树中查找键为 k 的节点,若不存在,则返回 end();否则返回指向着第一
	 *  个键为 k 的节点的迭代器(关于"第一个"的解释,参考 _M_lower_bound()).
	 */
	iterator
	find(const key_type &k){
		iterator j = _M_lower_bound(_M_begin(),_M_end(),k);
		// 此时若 j 不为 end(),则 j->key >= k,即 compare(j->key,k)==false
		// 而我们希望 j->key==k;所以需要 k >= j->key,即 compare(k,j->key) 也为
		// false,所以 k 存在的条件是: j != end() && compare(k,j->key)==false;
		if( j==end() || _M_impl._M_key_compare(k,_S_key(j._M_node)) )
			return end();
		return j;
	}

	/**
	 *  该函数的行为等同于如下语句:
	 *  return (_M_lower_bound(_M_begin(),_M_end(),k),
	 *			_M_upper_bound(_M_begin(),_M_end(),k));
	 */
	pair<iterator,iterator>
	equal_range(const key_type &k){
		_Link_type x = _M_begin();
		_Link_type y = _M_end();
		while( x!=0 ){
			// 此时 x->key < k,所以往右子树寻找;
			if(_M_impl._M_key_compare(_S_key(x),k))
				x = x->_M_right;
			// 否则此时表明 x->key>=k;所以往左子树寻找,注意在循环过程中始终保持
			// y->key > k(除非 y==_M_end());所以当找到 x,且 x->key == k 时,若
			// 此时 x 没有右子树,则 y 所指的节点就是 x 的后继!
			else if(_M_impl._M_key_compare(k,_S_key(x))){
				// 当 x->key > k 时,更新 y 的值
				y = x;
				x = x->left;
			}else{
				// 此时 x->key == k;然后利用 _M_lower_bound() 寻找第一个为 k 的
				// 节点,再利用 _M_upper_bound() 寻找第一个比 k 大的节点(即后继).
				// 在调用 _M_lower_bound() 时,为了减少搜寻次数,从 x 的左子树开始
				// 查找;
				_Const_Link_type xu = x;
				_Const_Link_type yu = y;
				y = x;
				x = x->_M_left;
				xu = xu->right;
				return make_pair(_M_lower_bound(x,y,k),
								 _M_upper_bound(xu,yu,k));
			}
		}
		return make_pair(y,y);
	}

	/**
	 *  若 val 中的键在红黑树中已经存在,则返回(键所在节点的迭代器,false).
	 *  否则,将 val 插入到红黑树中,然后返回(val 所在节点的迭代器,true).
	 */
	pair<iterator,bool>
	_M_insert_unique(const value_type &val){
		pair<_Base_ptr,_Base_ptr> res =
			_M_get_insert_unique_pos(KeyOfVal()(val));
		if(res->second != 0){
			_Alloc_node nodeGen(*this);
			return pair<iterator,bool>(
				_M_insert_(0,res->second,val,nodeGen),
				true);
		}
		return pair<iterator,bool>(
				iterator(static_cast<_Link_type>(res->first)),
				false);
	}

	/// 将 val 插入到红黑树中,并返回插入后,val 所在节点的迭代器	iterator
	_M_insert_equal(const value_type &val){
		pair<_Base_ptr,_Base_ptr> res = _M_get_insert_equal_pos(
			KeyOfValue()(val));
		_Alloc_node nodeGen(*this);
		return _M_insert_(0,res.second,val,nodeGen);
	}

	/// 移除 x 指向的节点.
	void
	erase(iterator x){
		_M_erase_aux(x);
	}

	/// 移除在红黑树中,所有键为 key 的节点,并返回被移除的节点个数
	size_type
	erase(const key_type &key){
		pair<iterator,iterator> range = equal_range(key);
		size_type old_size = size();
		erase(range.first,range.second);
		return old_size-size();
	}

	/// 移除 [first,end) 范围内的所有节点
	void
	erase(iterator first,iterator end){
		_M_erase_aux(first,end);
	}

private:
	/**
	 *  移除 nodeIter 迭代器指向的节点.此时需要
	 *  1. 维护红黑树的性质不变.
	 *  2. 维护 _M_impl._M_header,_M_impl._M_node_count 的值
	 *  3. 释放 nodeIter 迭代器所占的节点的内存.
	 */
	void
	_M_erase_aux(const_iterator nodeIter){
		_Base_ptr y = _Rb_tree_rebalance_for_erase(
			const_cast<_Base_ptr>(nodeIter._M_node),
			_M_impl._M_header);
		_M_drop_node(static_cast<_Link_type>(y));
		--_M_impl._M_node_count;
		return ;
	}

	/**
	 *  移除 [first,end) 范围内的节点,同 _M_erase_aux(const_iterator),只不过
	 *  此时移除了多个节点.
	 */
	void
	_M_erase_aux(const_iterator first,const_iterator end){
		// 此时作了优化,不再是一一移除,避免了每次移除后的调整.
		if(first == begin() && end == this->end())
			clear();
		else{
			for(; first!=end; ++first)
				erase(first);
		}
		return ;
	}

};// class _Rb_tree;


/**
 *  判断两棵红黑树是否相同,两棵树相同的条件是具有相同个数的节点数,并且
 *  按顺序比较所有的节点也相同(按顺序比较是指按中序遍历的顺序).
 */
template<typename Key,typename Val,typename KeyOfVal,typename Compare,
		 typename Alloc>
inline bool
operator==(const _Rb_tree<Key,Val,KeyOfVal,Compare,Alloc> &left,
		   const _Rb_tree<Key,Val,KeyOfVal,Compare,Alloc> &right);



};// namespace std;

#endif // org_wxw_std_study_include_bits_stl_tree_h_
